package graphmanip.collapsing;

import java.util.ArrayList;

import commonfunctions.Matrix;

import graphmanip.CollapsingMethod;

public class ClumpingCollapsing extends CollapsingMethod {

	@Override
	public ArrayList<ArrayList<Integer>> collapse(Matrix weights) 
	{
		ArrayList<Integer> seenNodes = new ArrayList<Integer>();
		ArrayList<ArrayList<Integer>> output = new ArrayList<ArrayList<Integer>>();
		
		for (int i = 0; i < weights.length(); i++)
		{
			ArrayList<Integer> groupedNodes = new ArrayList<Integer>();
			ArrayList<Integer> toGroupNodes = new ArrayList<Integer>();
			if (!seenNodes.contains(i))
			{
				toGroupNodes.add(i);
				while(toGroupNodes.size() > 0)
				{
					int thisNode = toGroupNodes.remove(0);
					seenNodes.add(thisNode);
					groupedNodes.add(thisNode);
					for (int j = 0; j < weights.length(); j++)
					{
						if (!groupedNodes.contains(j) && !toGroupNodes.contains(j) && 
								(weights.get(j, thisNode) > 0.0 || weights.get(thisNode, j) > 0.0))
							toGroupNodes.add(j);
					}
				}
				boolean shouldGroup = true;
				for (int j = 0; j < groupedNodes.size(); j++)
				{
					for (int k = j + 1; k < groupedNodes.size(); k++)
					{
						if (weights.get(j, k) < 0.0)
						{
							shouldGroup = false;
							break;
						}
					}
					if (!shouldGroup)
						break;
				}
				if (shouldGroup && groupedNodes.size() > 1)
					output.add(groupedNodes);
			}
		}
		
		return output;
	}

}
